<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        //给一个有序数组，无重复元素，还有一个target值，找出target在数组中的位置，如果不存在该元素，返回在数组中插入元素的位置
        // function getPos(arr, target) {
        //     let l = arr.length;
        //     let i = 0,
        //         j = l - 1,
        //         mid;
        //     while (i <= j) {
        //         mid = parseInt(i + (j - i) / 2);
        //         if (arr[mid] == target) return mid;
        //         else if (arr[mid] < target) {
        //             if (mid + 1 < l && arr[mid + 1] > target || mid == l - 1) {
        //                 return mid + 1;
        //             } else {
        //                 i = mid + 1;
        //             }
        //         } else {
        //             if (mid - 1 >= 0 && arr[mid - 1] < target || mid == 0) {
        //                 return mid;
        //             }
        //             j = mid - 1;
        //         }
        //     }
        // }

        // let arr = [2, 4, 6];
        // console.log(getPos(arr, 10));

        //普通二分法
        var arr = [1, 2, 3, 4, 5, 6];

        function getIndex1(arr, key) {
            let low = 0;
            let high = arr.length - 1;
            while (low <= high) {
                let mid = Math.floor((low + high) / 2);
                if (key == arr[mid]) {
                    return mid;
                } else if (key > arr[mid]) {
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
            return -1
        }
        console.log(getIndex1(arr, 4)); //4
    </script>
</body>

</html>